# -*- coding: utf-8 -*-
# @Author: shj
# @Date: 2019-03-22 11:24:21
# @LastEditTime: 2020-04-10 19:15:16
# @LastEditors: shj
# @Description: 冒泡排序
# @FilePath: /python3/algorithms/BubbleSort.py
"""
冒泡排序

1、比较相邻的元素。如果第一个比第二个大，就交换他们两个。
2、对每一对相邻元素作同样的工作，从开始第一对到结尾的最后一对。
这步做完后，最后的元素会是最大的数。
3、针对所有的元素重复以上的步骤，除了最后一个。
4、持续每次对越来越少的元素重复上面的步骤，直到没有任何一对数字
需要比较。

最坏时间复杂度	O(n^{2})
最优时间复杂度	 O(n)
平均时间复杂度	O(n^{2})
最坏空间复杂度	总共 O(n)，需要辅助空间 O(1)
"""


def select_sort(nosort_list):
    '''sort the nosort list by sequence'''
    r = nosort_list[:]  # 对原列表切片
    for i in range(len(nosort_list)):  # 取“第一个”元素
        for j in range(i + 1, len(nosort_list)):  # 取“第二个”元素
            # 元素r[i]的值小于r[j]交换值
            (r[i], r[j]) = (r[i], r[j]) if r[i] < r[j] else (r[j], r[i])
    return r


def main():
    nosort_list = [12, 3, 3, 3, 3, 34, 56, 21, 55, 4, 7, 51]
    sorted_list = select_sort(nosort_list)
    # 输出排序前后的列表
    print(f'the nosort_list = {nosort_list}\nthe sorted_list = {sorted_list}')


if __name__ == "__main__":
    main()